/**
 * \file HandleMap.h
 * \brief Hashtable based handle map
 * \author Corey Tabaka
 */

/*
   Copyright 2006 Corey Tabaka

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*/

#include <ktypes.h>
#include <Sync.h>
#include <hash.h>

#include <i386/mem.h>

#ifndef __USER_HANDLEMAP_H__
#define __USER_HANDLEMAP_H__

typedef unsigned int handle_t;

template <class value_type>
class HandleMap {
	protected:
	
	uint count;
	uint capacity;
	uint maxLoad;
	uint indexMask;

	typedef struct _record {
		bool used;
		handle_t key;
		value_type value;
	} record_t;
	
	record_t *records;
	
	Mutex lock;
	
	/**
	 * Find the least power of two that is equal or greater than argument.
	 * Valid arguments are in the range of 0 to 0x7fffffff.
	 */
	static uint NLP2(uint val) {
		val &= 0x7fffffff;
	
		uint i;
		for (i=0x40000000; i > 1; i >>= 1) {
			if ((i & val) == i) {
				break;
			}
		}
	
		return val > i ? i << 1 : i;
	}
	
	static uint hash(handle_t handle) {
		return joaat_hash((uint8 *) &handle, sizeof(handle_t));
	}
	
	void checkLoad(void) {
		uint load = count * 100 / capacity;
		
		if (load >= maxLoad && capacity < 0x80000000) {
			// save the current values
			record_t *trecords = records;
			uint tcapacity = capacity;
			
			// update the capacity to the next power of two
			capacity <<= 1;
			indexMask = capacity - 1;
			
			records = new record_t[capacity];
			memset(records, 0, sizeof(record_t) * capacity);
			
			// rehash records into the new array
			for (uint i=0; i < tcapacity; i++) {
				if (!trecords[i].used) {
					continue;
				}
				
				uint hashIndex = hash(trecords[i].key) & indexMask;
				uint index = hashIndex;
				do {
					if (!records[index].used
						|| records[index].key == trecords[i].key) {
						records[index].used = true;
						records[index].key = trecords[i].key;
						records[index].value = trecords[i].value;
						
						break;
					}
					
					index = (index + 1) & indexMask;
				} while (index != hashIndex);
			}
			
			delete [] trecords;
		}
	}
	
	public:
	
	HandleMap(uint initCapacity=1024, uint initMaxLoad=85) : lock() {
		capacity = initCapacity >= 2 ? NLP2(initCapacity) : 2;
		maxLoad = initMaxLoad < 100 ? initMaxLoad : 100;
	
		count = 0;
		indexMask = capacity - 1;
		records = new record_t[capacity];
	
		memset(records, 0, sizeof(record_t) * capacity);
	}
	
	~HandleMap(void) {
		for (uint i=0; i < capacity; i++) {
			if (records[i].used) {
				records[i].value = value_type(0);
			}
		}
		
		delete [] records;
	}
	
	void put(handle_t key, value_type value)  {
		lock.lock();
		
		uint hashIndex = hash(key) & indexMask;
		uint index = hashIndex;
		do {
			if (!records[index].used || records[index].key == key) {
				records[index].used = true;
				records[index].key = key;
				records[index].value = value;
				count++;
				
				break;
			}
			
			// use linear probing to find an available slot. wrap around at the end
			// of the array until we get back to the initial hashIndex (shoudln't
			// get there if count != capacity).
			index = (index + 1) & indexMask;
		} while (index != hashIndex);
		
		checkLoad();
		
		lock.unlock();
	}

	bool get(handle_t key, value_type &value) {
		lock.lock();
		bool ret = false;
		
		uint hashIndex = hash(key) & indexMask;
		uint index = hashIndex;
		do {
			if (records[index].used && records[index].key == key) {
				value = records[index].value;
				ret = true;
				
				break;
			}
			
			index = (index + 1) & indexMask;
		} while (index != hashIndex);
	
		lock.unlock();	
		return ret;
	}
	
	bool remove(handle_t key) {
		lock.lock();
		
		bool ret = false;
		
		uint hashIndex = hash(key) & indexMask;
		uint index = hashIndex;
		do {
			if (records[index].used && records[index].key == key) {
				records[index].value = value_type(0);
				records[index].used = false;
				ret = true;
				count--;
				
				break;
			}
			
			index = (index + 1) & indexMask;
		} while (index != hashIndex);
		
		// TODO: check load and reduce array size if capacity is below threshold
		
		lock.unlock();
		return ret;
	}
	
	bool containsHandle(handle_t key) {
		lock.lock();
		
		bool ret = false;
		
		uint hashIndex = hash(key) & indexMask;
		uint index = hashIndex;
		do {
			if (records[index].used && records[index].key == key) {
				ret = true;
				
				break;
			}
			
			index = (index + 1) & indexMask;
		} while (index != hashIndex);
		
		// TODO: check load and reduce array size if capacity is below threshold
		
		lock.unlock();
		return ret;
	}
	
	uint getCapacity(void) {
		return capacity;
	}
	
	uint getCount(void) {
		return count;
	}
	
	void status(void) {
		lock.lock();
		
		/*Log::printf(LOG_LOW, "HandleMap:\n");
		Log::printf(LOG_LOW, "    %u element capacity\n", capacity);
		Log::printf(LOG_LOW, "    %u current elements\n", count);
		Log::printf(LOG_LOW, "    %u%% load\n", count * 100 / capacity);
		Log::printf(LOG_LOW, "    %08x index mask\n", indexMask);*/
		
		lock.unlock();
	}
};

#endif
